#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 *
 *547. 省份数量
中等
947
相关企业
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2


 1 1 0 0
 1 1 0 0
 0 0 1 0
 0 0 0 0
 * */
vector<int> used;

// 思路从一个点开始遍历遍历和他连通的 点 并标记已经访问 然后num++  然后从下一个点开始
void dfs(vector<vector<int>> &isConnected, int col) {
    //这个不需要漫无目的的遍历 搞一个for 循环就行 因为有固定的点
    //表示行
    for (int i = 0; i < isConnected.size(); ++i) {
        if (used[i] != 1 && isConnected[i][col] == 1) {
            used[i] = 1;
            dfs(isConnected, i);//这个如果是+1 那么本列的其他位置不能被遍历了
            //这一点挺坑的
        }
    }
}

int findCircleNum(vector<vector<int>> &isConnected) {
    int count = 0;
    used.resize(isConnected.size(), 0);
    //列
    for (int i = 0; i < isConnected.size(); ++i) {
        if (used[i] == 0) {
            dfs(isConnected, i);
            count++;
        }
    }
    return count;
}